#define  _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cmath>
#include<algorithm> 
#include<queue>
#include<string>
#include<math.h>
#include<stack>
#include<vector>
#include<set>
#include<unordered_set>
#include<unordered_map>
using namespace std;
template<class k>
class hashfunc
{
public:
	size_t operator()(const k& key)
	{
		return (size_t)key;
	}
};
template<>
class hashfunc<string>//模板特化
{
public:
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto ch : key)
		{
			hash += ch;
			hash *= 131;
		}
		return hash;
	}
};
template<class k, class v>
class hashnode
{
public:
	hashnode(const pair<k,v>& kv):
		_kv(kv),
		_next(nullptr)
	{}
	pair<k, v> _kv;
	hashnode<k,v>* _next;
};
template<class k,class v,class hash=hashfunc<k>>
class hashtable
{
public:
	typedef hashnode<k,v> node;
	hashtable()
	{
		_table.resize(__stl_next_prime(0));
		_size = 0;
	}
	node* find(const k& key)
	{
		size_t hash0 = hs(key) % _table.size();
		node* pcur = _table[hash0];
		while (pcur != nullptr && pcur->_kv.first != key)
			pcur = pcur->_next;
		return pcur;
	}
	bool erase(const k& key)
	{
		size_t hash0 = hs(key) % _table.size();
		node* pcur = _table[hash0];
		node* prev = nullptr;
		while (pcur)
		{
			if (pcur->_kv.first == key)
			{
				if (prev == nullptr) // 删除头节点
					_table[hash0] = pcur->_next;
				else
					prev->_next = pcur->_next;
				delete pcur;
				_size--;
				return true;
			}
			prev = pcur;
			pcur = pcur->_next;
		}
		return false;
	}
	bool insert(const pair<k,v>& kv)
	{ 
		if (find(kv.first)) return false;
		if (double(_size) / double(_table.size()) >= 1)//扩容
		{
			unsigned long newsize = __stl_next_prime(_table.size() + 1);
			hashtable<k, v> newtable;
			newtable._table.resize(newsize);
			for (int i = 0; i < _table.size(); i++)
			{
				node* pcur = _table[i];
				while (pcur)
				{
					newtable.insert(pcur->_kv);
					pcur = pcur->_next;
				}
			}
			_table.swap(newtable._table);
		}
		node* newnode = new node(kv);
		size_t hash0 = hs(kv.first) % _table.size();//头插
		newnode->_next = _table[hash0];
		_table[hash0] = newnode;
		_size++;
		return true;
	}
private:
	vector<node*> _table;
	size_t _size = 0;
	hash hs;
	unsigned long __stl_next_prime(unsigned long n)
	{
		static const int __stl_num_prime = 28;
		static const unsigned long __stl_prime_list[__stl_num_prime] =
		{
			53, 97, 193, 389, 769,
			1543, 3079, 6151, 12289, 24593,
			49157, 98317, 196613, 393241, 786433,
			1572869, 3145739, 6291469, 12582917,25165843,
			50331653, 100663319, 201326611, 402653189,805306457,
			1610612741, 3221225473, 4294967291
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_prime;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}
};
int main()
{
	hashtable<string, string> ht1;
	ht1.insert({ "string","字符串" });
	ht1.insert({ "erase","删除" });
	ht1.insert({ "sort","排序" });
	ht1.insert({ "find","查找" });
	cout << ht1.find("string")->_kv.second << endl;
	ht1.erase("erase");
	cout << ht1.find("erase");
	hashtable<int, int> ht2;
	for (int i = 0; i < 53; i++)
		ht2.insert({ i,i });
	ht2.insert({ 97,97 });
	return 0;
}

